1. Field of the Invention
The present invention relates generally to flow control methodologies in communications networks, and more specifically to a shared memory packet switching device providing starvation free flow control functions.
2. Description of the Prior Art
Flow control relates to point to point traffic between a sending node and a receiving node in a network. In general, flow control methodologies provide for assuring that a fast sending node does not transfer data faster than the receiver can absorb it. Flow control typically involves some direct feedback from the receiving node to the sending node to tell the sending node how things are doing at the receiving end. One type of flow control method provides for a receiving node to assert backpressure on a sending node that is sending data too fast for the receiving node to handle. Typically, upon a determination by the receiving node that the sending node is sending data too fast, the receiving node will transmit a pause message to the sending node to instruct the sending node to pause in sending data to the receiving node. Sometimes, the sending node does not respond to the pause message and continues to send data to the receiving node which can lead to problems further discussed below. Another type of flow control method is packet dropping wherein packets, received from a sending node that cannot be processed by the receiving node, are simply dropped.
FIG. 1 shows a schematic circuit block diagram illustrating a prior art shared memory packet switching device at 10 operating in accordance with conventional networking management flow control methods including a conventional backpressure assertion process, and/or a conventional packet dropping process. The device 10 includes: a plurality of N receive ports 12 designated RX0, RX1, RX2, . . . RXn-1; and a plurality of N transmit ports 14 designated TX0, TX1, TX2, . . . TXn-1. Typically, each of the receive ports 12 and associated ones at the transmit ports 14 are formed by associated bi-directional ports that are communicatively coupled with associated ones of a plurality of network nodes (not shown) via associated network links (not shown).
The device 10 also includes: a switch control unit 16 communicatively coupled with each of the receive ports and with each of the transmit ports; and a shared memory unit 18 communicatively coupled with the control unit 16 as shown by a line 20. The control unit 16 typically provides packet routing functions for determining destination ports for each data packet received at the received ports, and also provides for temporarily storing and accessing the received data packets to and from the shared memory unit 18. The control unit 16 also typically provides destination port arbitration, and flow control processes such as packet dropping and assertion of backpressure.
Flow control problems may arise at the switching device 10 during operation in a network of a sending note (not shown) sends data packets to the switching device at a rate that overloads the switching device. To illustrate an exemplary network flow control problem, assume that receive port RX0 has a bandwidth of 100 Mbps, transmit port TX1 has a bandwidth 100 Mbps, and transmit port TX2 has a bandwidth of 10 Mbps. Consider also that half of the data packets being received at receive port RX0 are to be transmitted via port TX1 as indicated by a line 24, and the other half of the packets being received at port RX0 are to be transmitted via port TX2 as indicated by a line 26. In this case, the shared memory unit 18 will be filled with a large number of packets to be transmitted via port TX2 because the bandwidth of the receive port RX0 is much greater than the bandwidth of the transmit port TX2. Therefore, port TX2 is said to be congested. Because the memory space of the shared memory unit 18 is limited, a fairness problem arises if an excess amount of the memory space is used for storing packets received by a particular one of the receive ports 12 because the other receive ports 12 also require memory space of the shared memory unit for buffering received data packets. Therefore, the receive port RX0 will ultimately reach a “full” or “saturated” state if a threshold number of packets received at port RX0 are currently stored in the shared memory unit.
In accordance with one solution to this problem, the switching device 10 may assert backpressure on the source nodes (not shown) sending data packets to port RX0 by sending a pause message via the associated transmit port TX0 (which is communicatively coupled with the same network link as the receive port RX0) to the sending nodes instructing the sending nodes to pause in sending data packets. However, the sending nodes may or may not recognize the pause message in which case an excess amount of data packets received at port RX0 and destined for port TX2 will soon fill the shared memory unit 18. Another solution to this problem provides for dropping all packets received at port RX0 after port RX0 reaches the full condition. However, by dropping all packets received at port RX0, all of the traffic between port RX0 and port TX1 will be blocked. In this case, port TX1 is said to be starved.
What is needed is a method and apparatus for providing starvation free flow control in a shared memory switching device.